perm filename DRAFT[AIM,DBL] blob
sn#130839 filedate 1974-11-16 generic text, type T, neo UTF8
00100 .DEVICE XGP
00200
00300 .FONT 1 "FIX25"
00400 .FONT 2 "SIGN57"
00500 .FONT 3 "SHD40"
00600 .FONT 4 "BDI25"
00700 .FONT 5 "NGR20"
00800 .TURN ON "↓_π{"
00900 .TURN ON "⊗" FOR "%"
01000 .MACRO B ⊂ BEGIN VERBATIM GROUP ⊃
01100 .MACRO E ⊂ APART END ⊃
01200 .TABBREAK
01300 .COMPACT
01400 .SELECT 1
00100 .PORTION TITLEPAGE
00200 .EVERY FOOTING(,⊗5{DATE}⊗*,)
00300 .BEGIN CENTER
00400 .RETAIN
00500 .PAGE FRAME 54 HIGH 91 WIDE
00600 .EVENLEFTBORDER←ODDLEFTBORDER←1000;
00700 .FONT 6 "SGN114"
00800 ⊗6 BEINGS:⊗*
00900
01000 ⊗2REPRESENTATION OF KNOWLEDGE
01100 AS INTERACTING MODULES
01200 ⊗*
01300
01400 ⊗4Applied to Automatic Program Synthesis⊗*
01500 .END
01600 .GROUP SKIP 10
01700 Fourth Draft: NOT FOR DISTRIBUTION
01800 .GROUP SKIP 10
01900 ⊗3DOUG LENAT
02000
02100 STANFORD UNIVERSITY
02200
02300 ARTIFICIAL INTELLIGENCE LABORATORY⊗*
02400
02500 .PORTION CONTENTS
02600 .GROUP SKIP 10
02700 ⊗2TABLE OF CONTENTS⊗*
02800 .GROUP SKIP 10
02900 .SELECT 1
03000 .B
03100 1. Abstract . . . . . . . . . . . . . . . . 1
03200 2. Introduction . . . . . . . . . . . . . . 2
03300 3. Theory: Ideas . . . . . . . . . . . . . 3
03400 4. Reality: Examples . . . . . . . . . . . 10
03500 5. Theory: Design. . . . . . . . . . . . . 15
03600 6. Reality: Examples . . . . . . . . . . . 19
03700 7. Reality: Results . . . . . . . . . . . . 23
03800 8. Theory: Conclusions . . . . . . . . . . 28
03900 9. Acknowledgements . . . . . . . . . . . . 32
04000 Appendix 1: BEING parts . . . . . . . . . A1.1
04100 Appendix 2: the BEINGs . . . . . . . . . A2.1
04200 Appendix 3: BEING usage . . . . . . . . . A3.1
04300 Appendix 4: CF program . . . . . . . . . A4.1
04400 Appendix 5: the dialogue creating CF . . A5.1
04500 Appendix 6: trial running of CF . . . . . A6.1
04600 Bibliography . . . . . . . . . . . . . . BIB.1
04700 .E
04800 .SELECT 1
00100 .PORTION ABSTRACT
00200 .PAGE FRAME 54 HIGH 74 WIDE
00300 .EVERY HEADING(⊗3BEINGS⊗*,,⊗4Doug Lenat⊗*)
00400 .EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {IF PAGE = 1 THEN 1 ELSE PAGE})
00500 .COUNT PAGE PRINTING "1"
00600 .NEXT PAGE
00700 .GROUP SKIP 10
00800
00900 ⊗21. ABSTRACT⊗*
01000 .GROUP SKIP 10
01100
01200 Knowledge may be organized as a community of interacting modules
01300 (e.g., ACTORS [Hewitt]), in which control also resides. By granting
01400 each module a complex structure, yet constraining that that structure
01500 be standard over all the modules, some new theoretical and
01600 experimental results were found. The domain of this research was
01700 heuristic automatic synthesis of inductive inference LISP programs.
01800 Since these modules, called BEINGs, are the only entities permitted
01900 to exist theoretically, the generated code must also be a community
02000 of BEINGs. Like the original pool, the newly synthesized BEINGS which
02100 comprise the target program can answer
02200 questions about themselves as they run. An experimental system was
02300 partially implemented. It synthesized a few programs from very
02400 restricted dialogues. Some unexpected problems were encountered, and
02500 some aspects which were considered ignorable seem not to be. The
02600 performance of the system is discussed, and a preliminary view of
02700 BEINGs assessed.
00100 .PORTION THESIS
00200 ⊗22. INTRODUCTION⊗*
00300
00400 This paper reports on a scheme (BEINGS)
00500 for representing knowledge,
00600 partially realized in an experimental system (PUP6) aimed at
00700 generating LISP programs from dialogues with the user. The methods
00800 employed in the programs'
00900 synthesis are not formal, but rather involve structuring of knowledge
01000 about programming, about the task domain, and about transfer of
01100 control. To date, PUP6 has synthesized three significantly different
01200 target programs: a concept formation program (similar to [Winston]),
01300 a grammatical inference program, and a simple information storage and
01400 retrieval on keys system
01500 (referred to as, respectively, CF, GI, and INF).
01600 Specification is via rigid,
01700 extended dialogues carried on with the user, in
01800 a small subset of English, in which the task is delineated and
01900 questionable details are discussed. The specification is partial,
02000 and the system makes assumptions continually. This is what is meant,
02100 in the sequel, by ⊗4Automatic Programming. Target program⊗* will refer
02200 to code which has been successfully generated by such a system.
02300 This will typically be written in the same language as the system itself.
02400 ⊗4Dialogue⊗* is the interactive communication between the user and the
02500 automatic programming system, which results in target code synthesis.
02600 Historically, the CF target program was first cleanly
02700 specified. Next, an annotated
02800 protocol was done, and the BEINGs needed to reproduce the reasoning
02900 present in that protocol were fasioned. Additions were made to PUP6
03000 before it could synthesize GI or INF.
03100 The main successes of the experiment were that the desired
03200 reasoning steps in the original protocol
03300 were actually simulated, most of the BEINGs were used
03400 in writing more than one of the programs, and the synthesized code
03500 could be interrupted and asked a few kinds of questions. The main
03600 defects were the inflexibility of the system to new dialogues, the
03700 inability for the user to add new, high-level, domain-specific
03800 knowledge, and the verbosity of the system. Some of these problems
03900 may arise from the annotated protocol technique employed to get the
04000 BEINGs initially, and not from anything inherent to the BEINGs
04100 representation.
04200 Our treatment will follow these lines: First, the ideas are
04300 presented, including a discussion of BEINGs. Examples are then
04400 provided to illustrate these concepts. The next section describes the
04500 implementation, and explains the choice of targets. Only then will
04600 performance be evaluated. From the experience with PUP6 are drawn
04700 several preliminary conclusions about both the utility of the BEINGs
04800 representation and about problems relevant to Automatic Programming.
04900 The appendices present further details, samples, and
05000 examples. First comes a description of each BEING part, then a
05100 summary of the knowledge contained in each BEING. Appendix 3 is a
05200 table of data recording how the BEING community interacts. The final
05300 appendices present excerpts from the CF program, from PUP6
05400 synthesizing CF, and from CF itself running.
00100 .NEXT PAGE
00200 .EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {PAGE},THEORY: IDEAS)
00300 ⊗23. THEORY: IDEAS⊗*
00400 How should knowledge be represented? Many researchers feel
00500 that a simple, uniform formalism should be used for all facts; others
00600 disagree, claiming that complexity of behavior both justifies and
00700 demands complexity of representation. The BEINGs concept may resolve
00800 this uniformity vs. structure controversy; at the least, it is a
00900 compromise. One must recognize the advantages of each side, and
01000 refuse to give them up. The benefits of the former include easy
01100 addition of knowledge [Newell] and simple, aesthetic methods for
01200 combining information [McCarthy]. Structure, however, is necessary
01300 for (⊗4combinatorially⊗*) efficient handling of large amounts of data
01400 (see the real world; also
01500 [MIT]). PUP6 integrates these two ideas into the concept of BEINGs. A
01600 BEING is a collection of about thirty little bits of INTERLISP
01700 [Teitelman] code; the answers to thirty questions about the BEING.
01800 That is, a BEING is a small, loosely-knit LISP program, which is
01900 considered equivalent to its answers to these fixed questions. Every
02000 scrap of knowledge and all control structure should be encoded
02100 into BEINGs. There should be nothing else in the system but this
02200 interacting community.
02300 PUP6 embodies only some of the ideas and constraints
02400 discussed in this section. For example, economy demanded some very
02500 fast auxilliary functions, demons, and pure data structures. These
02600 reduced the computation time by a fixed factor (proportional
02700 to the total number of BEINGs in the system), by
02800 saving on the overhead implicit in each nondeterministic
02900 call to a BEING; they did not
03000 therefore reduce the ⊗4combinatorial⊗* effort involved. This will be
03100 explained in the REALITY section, along with any other deviations of
03200 PUP6 from an ideal BEINGs community.
03300 Notice that while each BEING is highly structured, this
03400 structure is standard over the entire pool. Each BEING part is itself
03500 a little BEING, etc., and this infinite regress stops when the
03600 contents of a BEING part becomes sufficiently primitive. As will be
03700 discussed later, the BEINGs mimic a human programmer; whatever he
03800 considers primitive when writing the program, BEINGs may consider
03900 primitive. Typically this level is about the same as the INTERLISP
04000 language: a primitive is a single INTERLISP function
04100 call, or a few simple ones connected trivially. Each BEING is
04200 cognizant of the set of thirty questions, in the sense that in
04300 answering one of them it may freely ask questions of other BEINGs
04400 (often through nondeterministic goal statements.) A few of the
04500 BEING-PARTS might be: what is your basic idea and purpose, what
04600 effects do you have, how do you go about causing them, what must be
04700 ensured before you begin, how complicated are you, what is your
04800 chance of success, are you recursive, whom else might you transfer
04900 control to, what alternatives to you exist, what BEINGs are a little
05000 more/less general than you are, do you evaluate your arguments, what
05100 is the nature of the value you return, why do you exist, why do you
05200 want to be in control now, etc. The reader may wish to glance at
05300 Appendix 1, to see the particular set of questions which were
05400 actually settled upon. When he feels the urge for a concrete
05500 example, he should glance over pages 11-12 and Appendices 4 and 5.
05600 The delineation of this set of questions has much to do with
05700 the epistemology of programming. The BEING parts may be classified
05800 according to their usage. Each BEING part has two tasks: it may be
05900 ⊗4asked⊗* about something, and it may be ⊗4called⊗* on to do
06000 something. Each of these may involve asking and calling other parts
06100 of itself and of other BEINGs, but typically the second activity
06200 involves an extra level of evaluation. Some parts are relevant to
06300 only one of these functions; most are at least oriented more toward
06400 one than the other. For example, the ARGS part may be asked trivial
06500 questions about the arguments to the BEING, but its main role is to
06600 bind the arguments when the BEING is given control. In Appendix 1,
06700 the role of each part is described. The ask-oriented parts divide
06800 into categories based on why they are queried: to decide which BEING
06900 to pass control, to tell whether the BEING has a certain property, or
07000 to give a memorized English answer to the user under proper stimulation
07100 (examples of these three types are: WHEN, PREDICATE, WHAT).
07200 The BEINGs control themselves in a simple way. A very general
07300 BEING, SERVE_THE_USER, has control initially. In general, some BEING
07400 ⊗4B⊗* will be in control. Its BEING parts are assembled into an
07500 executable function, and it is run. During the course of its reign,
07600 ⊗4B⊗* will want things done and/or tested which it cannot manage by
07700 itself. This corresponds to when a normal program needs to call a
07800 subroutine. What ⊗4B⊗* does is to call on SATISFY by name, supplying
07900 a description of what is wanted. SATISFY assembles itself, asks the
08000 entire BEING pool "who can do this thing?", and collects a list of
08100 the reponders. SATISFY then calls CHOOSE_FROM by name, supplying
08200 this list and the original request. Each responder is asked why he
08300 should be allowed to go now (the WHEN part) and how costly he will be
08400 if he does go (the COMPLEXITY part.) The best responder BEING is then
08500 passed control. If he succeeds in his mission, SATISFY returns
08600 control to ⊗4B⊗*. Otherwise the remaining responders are compared and
08700 a new one is tried. If they all fail, then SATISFY tells ⊗4B⊗* that
08800 it has failed. ⊗4B⊗* then decides whether to try something else or to
08900 fail itself. In addition to these goal statements, there exists a
09000 "world" consisting of assertions and variables with values. These are
09100 regarded as trivial cases of BEINGs, possessing only one part. So
09200 ⊗4B⊗* may also query this data base by saying "what assertions match
09300 this one...", or by asking "what is the value of...". These actions
09400 can be programmed in a much more efficient manner than as BEINGs.
09500 Since they never employ nondeterministic transfers, they are faster by
09600 an amount proportional to the total number of BEINGs in the system.
09700 The CHOOSE_FROM and SATISFY BEINGs act as global schedulers, and
09800 detract from the equality proclaimed earlier for each BEING. This again
09900 touches on the philosophy of programming. Since the parts which reflect
10000 how desirable a BEING is at any given time are standard over all BEINGs,
10100 the mechanism for choosing the control successor will be about the same
10200 whoever is in control. Either this choice algorithm must be duplicated
10300 inside every BEING, or else a universal chooser BEING must be tolerated.
10400 It seems that one must have either duplication of knowledge or else
10500 factor out the common knowledge into some higher-level interaction
10600 BEINGs.
10700 Theory would indicate that BEINGs must be assembled by other
10800 BEINGs dynamically. In practice, the way a BEING's parts fit together
10900 is uniform over all the BEINGs at all times. Thus one simple function
11000 (or assembled BEING) can assemble all the BEINGs initially into LISP
11100 functions. The precise algorithm for doing this is discussed in
11200 section 4.2.
11300 BEINGs are the only entities permitted (theoretically) to
11400 exist in our system; ergo all our code must be written as BEINGs, and
11500 must be written by BEINGs.
11600 An obvious but crucial consequence is that ⊗4some⊗* BEING(s)
11700 must write new BEINGs. The significant point is
11800 that the BEING who knows about
11900 ⊗4X⊗* takes charge of generating BEINGs relating to ⊗4X⊗*. For
12000 example, the INSERT BEING can do inserting by one of a few
12100 algorithms, and he can also write (by specializing himself) more
12200 specific insert routines, and he can answer questions about
12300 inserting. This idea is analogous to any reliance upon experts (e.g.,
12400 [Feigenbaum]), and also reemphasizes the theme of any modular
12500 representation of knowledge.
12600 A second consequence is that the output code will have all
12700 the ⊗4types⊗* of "intelligence" that any BEING community has: it
12800 can write variations of itself, modify itself according to the user's
12900 complaints, and answer questions about what it is doing as it runs.
13000 The specialized code cannot, of course, write the full complement of
13100 programs the original system could write.
13200 In a similar vein, ⊗4some⊗* BEING(s) must do the translation
13300 of the users' quasi-English inputs into BEING-usable form. ↓_Each_↓
13400 BEING ⊗4X⊗* is charged with recognizing English related to ⊗4X⊗*.
13500 Thus translation
13600 consists of querying "who can recognize ..." and waiting for a
13700 response. For example, our INSERT BEING must also recognize and
13800 process phrases involving inserting, stack-pushing, and merging.
13900 A result of this treatment of natural language
14000 processing is that any phrase which can be translated can be acted
14100 upon, and any phrase which can't be translated probably ⊗4can't⊗*
14200 be acted upon (even if it is rephrased). Since patterns are used,
14300 if the global structure of the sentence is recognized, then the user
14400 need only be asked to clear up the difficult sub-parts.
14500 A few constraints are present which reflect new biasses more
14600 than new insights: one need not feel any reverence toward the
14700 exploratory anthropomorphic paradigm of programming
14800 (ignore details, catch them
14900 later by debugging). As in all programming,
15000 decisions continually crop up which
15100 the system is not able to resolve at the time. The BEINGs system
15200 should always spend a significant effort deferring the decision as
15300 long as possible. When, at last, no progress can be made without its
15400 resolution, and if the system is still unsure, then either the user
15500 settles the question or else a backtrack point is reluctantly set up.
15600 "Reluctant" means that it is the last of several alternatives which
15700 are tried.
15800 But often, by this time, some new information is present which
15900 enables the system to resolve the decision, thus reducing the amount
16000 of backtracking. If there are two or more decisions which can no
16100 longer be deferred, the system tackles first the one estimated to be
16200 the easiest (analogous to Occam's razor).
16300 The final prejudice is that most of the carelessness
16400 bugs can be eliminated through this deferral, feed-forward, and very
16500 precise record-keeping. Humans depend on their adaptability to
16600 compensate for limitations in their brain hardware (long write times
16700 for long-term memory and external memory, and limited short-term
16800 memory size force us to ignore details; see [Newell]) but there is no
16900 need for an ⊗4automatic⊗* programming system to do so. For example,
17000 when a list structure is first encountered, the system records
17100 warnings that it is undefined, no accesses, insertions, or deletions
17200 have been observed, and so on. Each such worry is weighted, and
17300 periodically the system resolves such warning notes -- especially
17400 near the completion of the target program.
17500 To understand why Automatic Programming is a good task for a
17600 BEINGs pool, it is necessary to defocus our interest momentarily.
17700 The BEINGs representation may be suitable for simulating any
17800 complex task ⊗4T⊗* involving frequent small interventions by various
17900 experts. In addition to writing programs, this activity could
18000 perhaps be as
18100 diverse as playing chess, running a business, simulating physical
18200 interactions, and playing volleyball. For the latter task, a
18300 BEINGs-based system might create a specialized BEING for each player,
18400 perhaps with a complexity vector indicating his abilities, reflexes,
18500 etc. The BEING in control would be the player hitting the ball. A
18600 specialized Choose-from BEING would decide who goes next,
18700 occasionally interpreting a tie between BEINGs vying for control as a
18800 collision on the court.
18900 There is one particular bias of BEINGs toward writing
19000 high-level programs, over other activities. The new BEINGs created
19100 during the execution of a specified task are kept distinct from the
19200 original set of BEINGs. Then a ⊗4program⊗* for task ⊗4T⊗* is
19300 accomplished by doing ⊗4T⊗* and then dumping the new BEINGs out onto
19400 a new file. The entire old BEINGs pool is then treated as the
19500 language supporting this file. As a corollary, asking a BEINGs-based
19600 system to write any subset of itself is the null task.
19700 Most programmers intentionally augment their code to aid in
19800 later debugging, modification, and readability by humans. These aids
19900 are typically comments, summaries, over-generalized subroutines,
20000 optional print statements, and runtime statistics. Recently, the
20100 structure of the program itself has also been
20200 recognized as a powerful
20300 manipulable element, affecting the accessability of the code, not just
20400 its length or running time.
20500 The length of any program written as a pool of
20600 BEINGs is several times as long as a clean hand-coded version. This
20700 extra code, the parts of each new BEING which are superfluous, may be
20800 viewed as well-organized self-documentation. They should improve the
20900 debugging, expansion, and accessibility (to alien users) of the
21000 synthesized code.
21100 Some assertions are so meaningful to the user,
21200 that they should be stored in the code itself, even if they are
21300 only temporary. At any time, the user
21400 may look at a piece of code; the comments present ⊗4then⊗* are all
21500 assertions pertaining to that piece of code at that time.
21600 BEINGS may use comments at several different levels. At the
21700 lowest level, each comment is merely a unique token; it may be
21800 inserted, removed, or searched for. Slightly better, the BEINGs
21900 system can ask "is there a comment involving ...". For this purpose, a
22000 constrained syntax for the comments should be developed. Otherwise
22100 (as, unfortunately in PUP6) each new comment must be attended to
22200 ad hoc. Still higher level
22300 usage of comments would occur if a BEING looked at a comment totally
22400 ignorant of it, and TRANSLATEd it into something meaningful.
22500 When imagining an ideal AP (automatic programming) system,
22600 one ability we might wish for is that it be able to input a
22700 well-documented program, glean pure programming knowledge from it,
22800 and transform this into a format it can use. Also, to improve
22900 itself, it should be capable of digesting a sample, valid AP dialog,
23000 and (perhaps through additional user interaction) modify itself so it
23100 could actually carry on that dialog.
23200 Another ideal to hope for is that the user be permitted to do whatever
23300 he can whenever he can; if he suddenly thinks of a stray caution, the
23400 AP system should accept it (e.g., "Oh, I might want to type in
23500 HALT instead of STOP, sometimes").
23600 BEINGs were not designed with
23700 these ideals in mind, and as a result they may be an
23800 insufficient framework for achieving this.
23900 By studying the difficulties of the implementation of the BEINGs
24000 ideas, isolating those due to poor programming from those due to
24100 poor ideas, enough may be learned to build the next system one
24200 qualitative step closer to this ideal.
24300 It is in this spirit that BEINGs
24400 are now contrasted against the concepts of ACTORs, CLASSes,
24500 FRAMES, HACKER, formal AP systems, and macro expansion schemes.
24600 ACTORS [Hewitt] provided the key concept of integrating
24700 uniformity of construction with sophistocation of behavior. There
24800 is a continuum, among modular knowledge schemes, of standardization of
24900 "message" types between modules. ACTORs have no restriction whatsoever
25000 on this format. Each module has its own, unique parts (types of
25100 answers). So each ACTOR must be aware of all the parts (message formats)
25200 of all the ACTORs it ever is going to communicate with.
25300 Adding a new module is thus conceptually intricate as
25400 well as practically difficult. CLASSes [..........] have a few standard
25500 parts, and the modules are arranged in groups, each of which has its
25600 own additional types of parts. Thus a module can ask ⊗4any⊗* other module
25700 one of a few universal questions, and it can ask any module in its group
25800 an additional set of questions. If it is permitted to know about other
25900 groups' special parts, then the same adding problem recurs. If it is
26000 denied such knowledge, it cannot access much of the knowledge in the
26100 pool. If one requires a completely universal set of message types, then
26200 most of them will be irrelevant to most modules. This is the price which
26300 BEINGs pay. Later, it will be shown that this superfluity is real and is
26400 marginally tolerable. The most devastating criticism of striving for a
26500 universal set of module questions is that all this does is push all the
26600 non-uniformity down into the values of these parts. The only retort is
26700 empirical: if a good partitioning of the questions can be found, then
26800 the internal structure of each part with the same name will be comparable,
26900 and the only communication necessary will be simple questioning of
27000 modules's parts.
27100
27200 FRAMES [Minsky] seems superficially similar to BEINGs, and
27300 are so amorphous that they actually could subsume BEINGs. There is a
27400 deep difference of philosophy and of intended usage, however.
27500 FRAMES intentionally have default values already (with no processing)
27600 filled in for each frame, and replaced only when necessary.
27700 This is akin to automatic programming by blind debugging, but is
27800 antithetical to the fastidious bookkeeping BEINGs philosophy. As an
27900 example, consider the writing of a short, recursive, list
28000 manipulation LISP program (reverse, flatten, assoc, alternate, etc.)
28100 A human, consulting the proper frame in his head, knows to ignore the
28200 base step for a while, then fill it in, usually as ⊗4if NIL, then
28300 NIL⊗*. The
28400 human makes this default synthesis, tries out the program, and looks
28500 closer (to fill in this "slot" properly) only if something calls his
28600 attention to it (such as a LISP error message:
28700 NON-NUMERIC ARG ⊗4NIL⊗*, e.g., if what was really needed was the base
28800 step ⊗4if NIL, then 0⊗*).
28900 A BEINGs system would
29000 also defer working on the base step, but could -- and would -- place
29100 a note about that deferral into the assertional warning base. Before
29200 thinking it was finished, the system would attend to that note
29300 carefully. This is not a criticism of FRAMES:
29400 they are meant to be a
29500 construct to model perception, and therefore the default concept
29600 makes sense for them. BEINGs are clearly non-anthropomorphic in their
29700 internal workings, and would be very awkward models of human
29800 perceptual mechanisms.
29900 HACKER [Sussman] differs from BEINGs in the same qualitative
30000 way as FRAMES do.
30100 The orientation of HACKER is to put together pieces of programs
30200 into something close to the final desired target, then try and run
30300 it. When errors result, they are analyzed and then patched. BEINGs
30400 is oriented toward writing bug-free code; what it writes must always
30500 coincide with its internal specifications of that code. The user may
30600 later change his mind, and a BEINGs system must be able to modify its
30700 own programs, but this process is much better defined than blind
30800 debugging. On the other hand, if a BEINGs system does have an
30900 unexpected bug in it, it may not be able to recover from it. One
31000 way to overcome this would be to include special recover-from-bugs
31100 BEINGs.
31200 The formal manipulation systems which also synthesize code
31300 are so different from BEINGs, that it is difficult to compare them.
31400 These logical systems (e.g., [Luckham]) attack an entirely different
31500 problem. Their task is specified rigorously in advance, and they
31600 proceed formally to search for a solution program. BEINGs are
31700 designed to work on a much higher level, heuristically. Each action
31800 is implicitly justified by the fact that the user can later describe
31900 to the system
32000 what is undesirable about the program it's generated. BEINGs should
32100 thus be tolerant of user ambiguity and error. Also, BEINGs are not
32200 limited to automatic programming.
32300 Like ⊗4any⊗* AP system which writes structured programs, the
32400 external behavior of a BEINGs system applied to this task is
32500 reminiscent of macro expansion regardless of ⊗4what⊗* the internal
32600 BEING interactions are. One major distinction between the two
32700 concepts is when and how the macros are expanded. Traditional answers
32800 are: at compile time, by rigid substitutions.
32900 BEINGs systems expand their "macros" at
33000 times they choose, using knowledge gleaned from each other and from
33100 the user. For example, consider a series of macro calls occurring in
33200 the code: (m1)(m2)(m3). A macro expander could expand these in any order,
33300 and the three activities could go on simulatneously, with no interference
33400 or change in the final code. BEINGs would try to find some task common
33500 to all three calls, and work on that first. The order of which to
33600 first expand fully would be carefully weighed,
33700 and during that expansion new
33800 information would be learned which could affect the expansions of the
33900 other two function calls. The final code would not simply be the APPEND
34000 of the expansions of m1, m2, m3. As macro expansion schemes increase
34100 in sophistocation, it may someday be appropriate to refer to BEINGs as
34200 such a system.
00100 .NEXT PAGE
00200 .EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {PAGE},REALITY: EXAMPLES)
00300 ⊗24. REALITY: EXAMPLES⊗*
00400 This section presents examples of the following: a
00500 programming knowledge BEING, an explanation of what happens when a
00600 BEING is called, a concept formation knowledge BEING, a description
00700 of a piece of the user-PUP6 dialogue, and some justification for
00800 using functions, call-by-name, demons, and assertions. Although these
00900 examples are meant to clarify the preceding section's theoretical
01000 ideas, they are all drawn from the actual PUP6 system.
01100 4.1. OBTAIN_USABLE_INFORMATION is a typical high-level,
01200 domain-independent BEING. The WHEN part consists of predicate
01300 "feelers" which sample the world and report their qualities
01400 numerically. A reason is supplied with each feeler:
01500 an English sentence stored for the benefit of inquisitive users.
01600 The numbers are
01700 then simply added to decide how a propos the BEING is at present.
01800 This scheme is adequate but undesirable; one would like them to
01900 discuss descriptions of what they encounter; but the WHEN part is
02000 used only to break ties between BEINGs vying for control, and it
02100 usually doesn't matter what order they go in. Thus a simple, fast
02200 method of selection suffices. This particular BEING
02300 has feelers which respond that it is ⊗4always⊗* an undesirable
02400 (with weight -10; see the actual WHEN part on page 12)
02500 thing to do, but ⊗4may⊗* be indicated (+111) if there exists
02600 new but not yet usable information. The possible final WHEN
02700 values are thus 111, 101, and -10. These numbers, like all the parts
02800 of all the BEINGs initally in PUP6, were decided upon and inserted by
02900 hand.
03000 The IDEN parts are collected together into a large
03100 translation table. When a form ⊗4LI⊗* must be translated, the
03200 TRANSLATE BEING goes through this table, asking each IDEN part if it
03300 claims to recognize ⊗4LI⊗*. Each IDEN runs its own little program,
03400 typically some type of pattern match involving ⊗4LI⊗* and the state
03500 of the world, to answer this question. Some measure of goodness of
03600 match is also reported. If there is more than one responder,
03700 CHOOSE-FROM picks the one with the highest priority of match. The
03800 winner runs a little program which ultimately returns a BEING-call or
03900 a constant as the translated value of ⊗4LI⊗*. This program might call
04000 other BEINGs, often calls TRANSLATE several times recursively on
04100 parts of ⊗4LI⊗*. Now examine the IDEN part of the
04200 OBTAIN_USABLE_INFORMATION BEING (next page).
04300 There are just two classes of phrases that this BEING can recognize.
04400 If two conditions are met,
04500 it says to ⊗4call⊗* OBTAIN-USABLE-INFORMATION with, as argument, the
04600 result of calling TRANSLATE on the second element of ⊗4LI⊗*.
04700 If some BEING or user wants to find out more about anything, then
04800 this BEING can be called with that thing as argument.
04900 The EFFECTS parts of each BEING are similarly collected into
05000 one table to facilitate asking all BEINGs simultaneously "Can you
05100 cause X to occur?" Each EFFECTS part examines X and the world, and
05200 either replies No, or else returns a little program (involving calls
05300 and constants) which should produce the effect, with a certain
05400 probability. This program will probably involve a call to the BEING
05500 itself. The BEING below shows that it should be called to acheive the
05600 existence of new, usable information (see the MAIN:EFFECTS part, page
05700 12).
05800 The WHAT, HOW, and WHY parts are mainly for the user's
05900 benefit. When a choice between BEINGs must be made, the WHEN,
06000 AFFECTS, and COMPLEXITY-VECTOR parts are queried. If a new,
06100 manipulated version of the BEING must be created, the
06200 SPECIALIZATIONS, ENCODABLE, DATA-STRUCTURE, PREDICATE, and
06300 FORM-CHANGING parts might be relevant. If the BEING fails, some
06400 BEING speicified in the ALTERNATIVES or GENERALIZATIONS parts might
06500 be tried.
06600 In the current case, the COMPLEXITY-VECTOR says that it is of
06700 average difficulty to call, its descendants may (.5 chance) call it
06800 back, it has an average chance of success and cost of attempting it,
06900 and there is no (.1) good reason to defer it any longer.
07000 The AFFECTS part of the OBTAIN_USABLE_INFORMATION BEING is
07100 clear. One BEING is definitely called, and four others might be.
07200 The absence of some parts, like DATA_STRUCTURE, PREDICATE,
07300 and NLAMBDA, indicate that these qualities don't apply. The absence
07400 of other parts, like SPECIALIZATIONS and ALTERNATIVES, indicate
07500 only a
07600 lack of thoroughness in filling out unneeded BEING parts.
07700 The META-CODE says to choose from the following four
07800 alternatives, each of which is itself a BEING:
07900 Get_Brand_New_Information (in English, from the user), Translate
08000 something (transform from English to BEING-calls),
08100 Analyze_The_Implications (of some existing, translated information),
08200 Extract_a_Relevant_Subset (of the existing information) to
08300 concentrate upon.
08400 Calls are nondeterministic only when the BEING doesn't know exactly
08500 which BEING to call. If the ⊗4set⊗* of possible choices is known, as
08600 in this case, then CHOOSE-FROM is called with the choice set explicit.
08700 If even this isn't known, then CHOOSE-FROM must query the EFFECTS
08800 parts of all the BEINGs in the system.
08900 Below are exhibited the actual representation of this BEING
09000 in PUP6, and the function which would be executed if it were
09100 ⊗4called⊗*.
09200
09300 .SELECT 5
09400 .BEGIN NOFILL
09500
09600
09700 ⊗4↓_PART_↓ ↓_actual value of the part for OBTAIN:USABLE:INFORMATION_↓ ⊗*
09800
09900 IDEN ((if you see: (AND (EQUAL (CAR LI)
10000 OBTAIN:USABLE:INFORMATION)
10100 (EQUAL (LENGTH LI)
10200 2))
10300 then return: (OBTAIN:USABLE:INFORMATION (TRANSLATE (CADR LI))))
10400 (if you see: (MATCH ( FIND OUT MORE ABOUT ANY1) LI)
10500 then return: (OBTAIN:USABLE:INFORMATION ANY1)))
10600 BEING T
10700 EXPLICIT:ARGS (U)
10800 WHAT ( OBTAIN SOME INFORMATION WHICH CAN BE USED)
10900 HOW ( OBTAIN NEW FACTS ABOUT OLD INFORMATION, OR OBTAIN TOTALLY
11000 NEW INFORMATION)
11100 WHY ( PUP HAS NO MORE INFORMATION THAT IT CAN USE TO PROGRESS)
11200 WHEN ((if T then add in -10 (SINCE THIS IS AN EXPONENTIALLY-GROWING,
11300 BAD THING TO DO IN GENERAL))
11400 (if NEW:INFO:LIST then add in 111
11500 (BECAUSE WE SHOULD WORK ON UNASSIMILATED NEW
11600 INFORMATION IF THERE IS ANY)))
11700 META:CODE (DO
11800 (CHOOSE:FROM ((TRANSLATE U)
11900 (GET:NEW:INFORMATION U)
12000 (ANALYZE:IMPLICATIONS U)
12100 (EXTRACT:RELEVANT:SUBSET U)))
12200 BECAUSE
12300 (WE CAN ONLY TRY TO OBTAIN USABLE
12400 INFORMATION IN ONE WAY AT A TIME))
12500 EXPLICIT:ARGS:CHECK T
12600 MAIN:EFFECTS ((to get (NEW INFO ANY1)
12700 do (OBTAIN:USABLE:INFORMATION ( ANY1)))
12800 (to get (USABLE INFO ANY1)
12900 do (OBTAIN:USABLE:INFORMATION ( ANY1))))
13000 AFFECTS ( (CHOOSE:FROM CALLED)
13100 (TRANSLATE POSSIBLE:CALLED)
13200 (GET:NEW:INFORMATION POSSIBLE:CALLED)
13300 (ANALYZE:IMPLICATIONS POSSIBLE:CALLED)
13400 (EXTRACT:RELEVANT:SUBSET POSSIBLE:CALLED) )
13500 COMPLEXITY:VECTOR (.5 .5 .5 .5 .1)
13600
13700 .SELECT 1
13800 4.2. When a BEING is ⊗4called⊗*, its parts are assembled into a
13900 function which is then executed. Here is the ⊗4FUNCTIONAL⊗* form of the
14000 OBTAIN:USABLE:INFORMATION BEING:
14100 .SELECT 5
14200
14300 (OBTAIN:USABLE:INFORMATION
14400 (LAMBDA (U FN:VALUE FINAL:CO:REQ)
14500 (PROG1
14600 (AND
14700 (SETQ BEING:STACK (CONS OBTAIN:USABLE:INFORMATION BEING:STACK))
14800 (PUT OBTAIN:USABLE:INFORMATION SPEC:WHY BECAUSE)
14900 (EVERY (APPEND CURRENT:DEMONS USER:INTERRUPT:DEMONS)
15000 (QUOTE APPLY*))
15100 (SETQ BECAUSE
15200 (QUOTE (WE CAN ONLY TRY TO OBTAIN USABLE
15300 INFORMATION IN ONE WAY AT A TIME)))
15400 (CHOOSE:FROM (QUOTE ((TRANSLATE U)
15500 (GET:NEW:INFORMATION U)
15600 (ANALYZE:IMPLICATIONS U)
15700 (EXTRACT:RELEVANT:SUBSET U)))))
15800 (SETQ BEING:STACK (CDR BEING:STACK)))))
15900 .END
16000 .SELECT 1
16100
16200 The process of assembling the BEING parts into a function is
16300 straight-forward. First, the explicit arguments (those global to the
16400 BEING) are bound. The implicit arguments (those local to the BEING,
16500 like PROG variables) are initialized. The name of the BEING is pushed
16600 onto the BEING control stack (pointing to its caller), and any
16700 newly-activated demons are pushed onto the demon stack. The
16800 ARGS-CHECK predicates are evaluated. Then PUP6 works to make each
16900 PRE-REQUISITE true in the world. Each COMMENT is evaluated, then the
17000 CO-REQUISITES, META-CODE, and current demons all are executed in
17100 pseudo-parallel. Each POST-REQUISITE is then satisfied. Since these
17200 activities are all embedded in an AND, any of them may cause the
17300 entire BEING to halt and fail, simply by returning NIL.
17400 In both cases, just before exiting, the demon
17500 stack is popped and the BEING stack is updated (usually just popped),
17600 and control passes to the delegated BEING (usually the one who called
17700 this BEING, at the state when he called it.) A fancy context
17800 mechanism was available but not actually needed.
17900 The function which assembled all the BEINGs exploited the
18000 fact that it operated only at system load time. Thus if the BEING
18100 had no new DEMONs to activate, all the corresponding demon-stack
18200 manipulations could be omitted. Optimizations like these are clear
18300 from comparing the functional form and the description of how it
18400 should be created (see above).
18500 Another example in this BEING is that no CO-REQUISITES
18600 occur, so no parallel processing need be simulated.
18700 4.3. PARTITION_A_DOMAIN is a high-level, domain-specific BEING
18800 whose basic idea is to divide up a space into categories. Only two
18900 BEING parts are filled in here which were absent from
19000 OBTAIN_USABLE_INFORMATION; namely, SPECIALIZATIONS and DEMONS. The
19100 SPECIALIZATIONS part says that to write a specific version of itself,
19200 a few decisions must be made. The results will then indicate what
19300 pieces of code get assembled together to form the new BEING. The
19400 partition may be only partial (an element of the domain belongs to no
19500 class of the partition), only weak (an element belongs to more than
19600 one class), and, most importantly, the specialized BEING should work
19700 by repeatedly doing some of the following three activities: accept a
19800 class-name from the user and guess some of its elements, accept an
19900 element from the user and try to guess which class it belongs to,
20000 or accept an <element, class-name> pair. Other BEINGs know
20100 about these accepting, guessing, checking activities.
20200 The DEMONS part says that during the partitioning, the only
20300 new demon to keep active is the one called Fringe_of_Consciousness.
20400 This name was chosen because its function is similar to the "impossibility"
20500 mentioned in [Dreyfus]. In the course of
20600 writing GI, the system learns that the main task is one of
20700 grammatical inference. The Grammatical_Inference BEING then asserts
20800 that if the user ever mentions the word TEST, he may actually mean
20900 PARSE. This is placed in the IDEN part of the TEST BEING, and is
21000 therefore only demonized, waiting on the periphery of PUP6's
21100 concentration. It is in fact triggered later in the dialogue, as an
21200 inference surprising to the user.
21300 4.4. The dialogue to synthesize CF begins by PUP6 asking the
21400 user for any task. The user replies, ⊗4Write a program which does
21500 concept formation⊗*. There are many decisions that PUP6 knows about in
21600 writing a specialized concept formation program [Hempel],
21700 and it manages to
21800 defer them all. For example, it must choose between classificatory,
21900 comparative, and metrical concept formation. Since all three involve
22000 partitioning a domain of examples, PUP6 decides it can defer this
22100 choice until after code for the partitioning is synthesized. The
22200 effort of the system is now directed toward this "piece" of the
22300 program. When it is completed, an hour or two later, the system asks
22400 the user to make this decision. When he picks the first alternative,
22500 which involves ⊗4only⊗* partitioning, the system prints that it has
22600 finished the entire CF task, and dumps the newly created BEINGs onto
22700 a file.
22800 4.5. Earlier, the claim was made that the presence of popular
22900 AI language features did not detract from the combinatorial behavior
23000 of the system, since BEINGs subsume each mechanaism used. This will
23100 now be sketched. Direct call by name may be viewed as a trivial type
23200 of pattern-directed call,
23300 where each BEING can recognize its own name. See the IDEN part of the
23400 OBTAIN:USABLE:INFORMATION BEING, for example.
23500 A demon
23600 in PUP6 is merely a function which gets executed periodically,
23700 and may occasionally trigger a BEING. This could be replaced by a
23800 BEING whose EXPLICIT:ARGS:CHECK part contains the triggering
23900 predicate, and whose META:CODE is simply a call by name directly to
24000 the BEING which is supposed to be activated.
24100 An assertion can be
24200 viewed as a BEING containing only an IDEN part; when the BEING
24300 recognizes a form which matches it, it returns the fully instantiated
24400 assertion.
24500 A function is equivalent to a BEING with only META:CODE,
24600 ARGS, and NLAMBDA
24700 parts; one knows almost nothing about it before executing it.
24800 Notice that
24900 the overheads saved by these mechanisms are substantial. For example,
25000 assertions replace an entire BEING call by a single CDR evaluation.
25100 The reader may have observed the static quality of these
25200 examples, and wished for one of BEINGs in action, passing control
25300 back and forth in order to do something. But to present a reasonable
25400 example of BEINGs interacting, it is necessary to understand
25500 something about the target task. Thus we describe PUP6 in the
25600 following section, including how the target task CF evolved. Then
25700 comes the dynamic example, in section 6.
00100 .NEXT PAGE
00200 .EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {PAGE},THEORY: DESIGN)
00300 ⊗25. THEORY: DESIGN⊗*
00400 A highly polished presentation of a large system omits
00500 mention of the design and implementation mistakes. This is
00600 unfortunate; many decisions which seem arbitrary are the result of
00700 painful re-working, and conversely. The reader may relax; he will
00800 find nothing polished about this treatment.
00900
01000 Once the task (automatic program synthesis from specific
01100 dialogue) was decided upon, considerable attention was spent on
01200 choosing an appropriate domain of target programs. The choice,
01300 inductive inference (II), merits discussion. The obvious
01400 difficulty appears to be the complexity of the programs involved:
01500 they are two orders of magnitude larger than any previously
01600 synthesized programs. But there are four big attractions:
01700 (i)
01800 A wide range of complexity exists, from a one-page sequence
01900 extrapolator to Meta-Dendral.
02000 (ii) Each increasingly
02100 sophisticated II program uses many of the concepts embodied in
02200 simpler II programs.
02300 (iii) If a super-human target program is
02400 ever written, it could itself contribute to the field of Automatic
02500 Programming! (This remark is humorous in the seventies, but may be
02600 commonplace someday.)
02700 (iv) Since people (especially those who write
02800 AI programs) are the inductive
02900 inference experts, our reliance on introspection is as
03000 valid -- and potentially as valuable -- as chemists' protocols were
03100 to Dendral.
03200 After studying many sample programs from the II domain,
03300 sequence extrapolation [Pilvar] seemed the most reasonable beginning
03400 task. It was quickly learned that this was too easy: humans have only
03500 a few techniques for extrapolating sequences, and a very limited
03600 capacity for composing them. Thus a rather rigid sequence
03700 extrapolator writer may be capable of generating a large class of
03800 super-human programs (see section 4.2 on
03900 Sequence-Extrapolator-Writer, in [Green]).
04000 The next candidates were grammatical inference and concept
04100 formation [Hempel].
04200 Determined not to choose too simple a task again, the
04300 latter program was finally decided upon. The particular target was a
04400 variant of [Winston]. To make the goal more tractable, certain parts
04500 of Winston's description were ignored, namely the heuristic
04600 graph-matching section, and the uniformity requirement that relations
04700 on features be functionally indistinguishable from features.
04800 This last phrase means that CF may internally
04900 store (MUSTNOT (SUPPORTS a b))
05000 differently from the representation of simple
05100 features like (TOUCHES a c).
05200 It seems instructive now to describe how the target program
05300 should operate. It repeatedly scans a scene and tries to name it. The
05400 scene is broken into a set of features and a set of objects. Each
05500 feature is a relation
05600 on one or more objects in the scene. Internally, the program
05700 maintains a model for each differently-named
05800 concept it has ever encountered. "Concept" here is used technically, to
05900 indicate a particular data structure maintained by the target program.
06000 The model contains a description of the objects expected in the
06100 scene, a set of features which must be present in the scene (else it
06200 can't be the same as this concept), a set of features which must not
06300 be present in the scene, and a set of features which may or may not
06400 be present. Thus a model is like an archtypical scene plus a name.
06500 Each time the program is confronted by a new scene, the program must
06600 scan its models until it finds one which matches it. A model is said
06700 to match a scene if all the MUST features associated with that model
06800 are present in the scene, and all the MUSTNOT features are
06900 absent from the observed scene. The target
07000 program informs the user of this guess,
07100 and accepts the proper concept name. If it guessed incorrectly, it
07200 modifies its models. The wrong guess model may have features added to
07300 its MUST or MUSTNOT sets; the correct concept name model may have to
07400 be modified or (if it's a new concept) created and inserted into the
07500 list of models. See the flowchart on page A4.7.
07600 .B
07700
07800 For example, part of a scene might be: OBJECTS a,b,c,d
07900 (GREEN a)(BLUE c)(TOUCHES c d)(SUPPORTS a c)(SUPPORTS b c).
08000
08100 A model for an arch might be: NAME ARCH
08200 OBJECTS a,b,c
08300 MUST (SUPPORTS a c)(SUPPORTS b c)
08400 MUSTNOT (TOUCHES a b)
08500 MAY (GREEN a)(WEDGE c)(PRISM a)(BLOCK b)(PARALLEL a b)
08600 .E
08700 Suppose that the target program reads in the above scene and
08800 tries to match it to the above model for consistency. The MUST
08900 relations should all be present. Yes, the scene does contain
09000 (SUPPORTS a c) and (SUPPORTS b c). Next, the MUSTNOT relations must
09100 be absent from the scene. Sure enough, (TOUCHES a b) isn't there. So
09200 the model and scene are consistent, and the program announces that its
09300 guess is ARCH.
09400 If the user verifies this guess,
09500 then the MAY set is augmented with (BLUE c) and (TOUCHES c d), and
09600 the OBJECTS set is augmented with "d."
09700 If the user denies that the scene is an arch,
09800 the target program
09900 sees if there are any relations in the model's MAY set which do not
10000 occur in the scene. If so, one of them (e.g., (PARALLEL a b)) will
10100 be transferred from the MAY to the MUST set. If no such feature
10200 existed, the program would look for a feature present in the scene
10300 but absent from all sets of the model (e.g., (BLUE c)), and insert
10400 it into the MUSTNOT set. Also, if the user disagreed with the guess,
10500 he would be asked what the true name of the concept was, and that
10600 concept's model would have its MAY set augmented by any new
10700 features in the scene. Any features on its MUST or MUSTNOT sets
10800 which contradicted the scene would be transferred to the MAY set.
10900 After the target concept formation program was specified, it
11000 was trimmed and then rewritten as a structured program [Gadwa]. Next,
11100 a complete dialogue was simulated between the user and a human
11200 programmer (referred to as the system-player) playing the role of an
11300 "intelligent" automatic programming system (similar to, e.g.,
11400 [Balzer]). The system-player kept careful records as he
11500 programmed, and tried to create a bug-free structured program. The
11600 dialogue was then annotated: after each user response, comments
11700 were inserted which described the "states" the system-player had gone
11800 through before printing his next response. This included blind paths
11900 which were tried, use of outside world knowledge, and, in general,
12000 was meant to be the "intelligence" necessary to do the task. The
12100 fear was that a system could be built which synthesized the concept
12200 formation program, and yet was so unintelligent that nothing was
12300 learned from it. (see section 4.1 on PW1, for example, in [Green]).
12400 Hopefully, any system which
12500 (i) got the target program correctly,
12600 (ii) followed this
12700 initial dialogue, and, most importantly, (iii) went
12800 through the same line of reasoning that the comments indicated the
12900 system-player
13000 followed, would be far along the road toward intelligence. A
13100 corollary of this incremental annotated protocol approach is that the
13200 abilities of the user must coincide with those of the subject who
13300 participated in the protocol (see also [Woods]). The system would be
13400 far along the road toward automatic programming if it also (iv) was
13500 able to write CF from several dialogues, from several users, with
13600 little preparation. PUP6 was not designed to do this, and in the end
13700 it proved to be a serious deficit. Henceforth, ⊗4protocol⊗* will
13800 refer to this user-player / system-player simulated dialogue.
13900 The target user must be familiar
14000 with LISP, well-grounded in computer science, and have the
14100 input/output behavior of the concept formation (CF) program very
14200 clearly in his mind. The natural language front end is so brittle
14300 that the user must also phrase his responses very similarly to those
14400 of the original protocol subject. This factor prevented dialogues
14500 from multiple users from being successful.
14600
14700 At this point, most of the ideas described in section 3
14800 surfaced, including a rough initial set of BEINGs. Each one had not
14900 much more than a name and a vague description of what it must do.
15000 The dialogue was cycled through again, painstakingly, and the
15100 comments were replaced by a description of which BEINGs would call
15200 which other BEINGs, why, and the results of each such call. The
15300 constraints on each BEING thus grew, sometimes changed, and
15400 occasionally a new BEING or BEING part had to be added to the
15500 community. This process was long (200 hours) and produced a long
15600 (200-page) protocol, actually a hand trace of the system execution.
15700 About eighty BEINGs were needed: a dozen domain-specific ones and
15800 the rest domain-independent programming knowledge. About thirty
15900 different BEING parts were called for, and they are listed in
16000 Appendix 1. The next appendix describes each BEING briefly; only the
16100 most important knowledge is mentioned.
16200 A result of this method of incremental specification of
16300 BEINGs is that each BEING has only those parts which are going to be
16400 used sometime during the ensuing dialogue. This seemed too specific,
16500 so some effort was spent filling out parts that weren't strictly
16600 necessary to write the concept formation program. Perhaps more
16700 careful attention to this activity would have made the system more
16800 tolerant of changes in the dialogue.
16900 During the course of massaging
17000 PUP6 into writing the other target programs, very few additional
17100 parts had to be added to existing BEINGs. Typically, either an old
17200 part had to be generalized or else a new BEING created. After writing
17300 CF, GI, and INF, there are now an even hundred BEINGs in PUP6.
17400 The data on how filled-out each BEING was -- and had to be --
17500 is presented in several forms, here and in the appendices. In
17600 Appendix 1, next to each BEING part is the percentage of BEINGs which
17700 had to have this part specified for them. Appendix 3 reveals how each
17800 BEING was actually used, including the number of its BEING parts
17900 which exist and were called upon during a dialogue. On the average,
18000 each BEING part was present in 36% of all BEINGs, and, also on the
18100 average, each BEING had 10.5 of its 29 parts specified. This says
18200 that each BEING was actually asked a third of all possible questions
18300 and that each question was needed in about a third of all the BEINGs.
18400 This is just marginally tolerable; if the percentages were much
18500 lower, then the idea of grouping the BEINGs and assigning each group
18600 its own distinct set of questions would be clearly called for.
18700 The principle that "everything is BEINGs" was relaxed in the
18800 interests of absolute CPU time and feasibility of coding. Besides
18900 BEINGs, PUP6 employs functions, demons and an assertional data base.
19000 During the programming, 100 small functions were written to
19100 supplement the language. Most were typical current AI language
19200 features [Bobrow] (pattern-matching, demons, special data types), or
19300 tiny additions to INTERLISP [Teitelman] (flatten, set-difference), or
19400 functions which manage BEINGs (add-a-new-being,
19500 print-a-being's-parts). Many of these features were simplified (and
19600 speeded up) by using the knowledge that PUP6 was to be an AP system.
19700 For example, all the different types of assertions that an AP system
19800 might want to make deal with different concerns of programming. Thus
19900 a group of about forty different assertion patterns could be fixed,
20000 each one becoming a named list; this almost eliminated searching
20100 during retrieval from the assertional base.
00100 .NEXT PAGE
00200 .EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {PAGE},REALITY: EXAMPLES)
00300 ⊗26. REALITY: EXAMPLES⊗*
00400
00500 An example of the PUP6 community of BEINGs interacting will now
00600 be presented. Let's jump one third of the way into the dialogue which
00700 writes CF. The system learns it must compare the input scene against
00800 its internally stored models of concepts, until it finds one which
00900 doesn't fail the comparison. It asks the user what it means for
01000 scene S to fail the comparison to model M. The user replies,
01100 whenever M is incompatible with the observed features of S.
01200 The IDEN part of the
01300 CONTRADICTS BEING recognizes this sentence pattern, and transforms it
01400 to
01500 .NOFILL
01600 (FORSOME F IN M_FEATURES (specialized:contradicts F S_FEATURES)).
01700 .FILL
01800 The BEING
01900 which inserts this into the synthesized code requires that the user
02000 pick some proper name for the function specialized:contradicts;
02100 this will be a streamlined contradiction test written by the
02200 CONTRADICTS BEING. Say the user reponds by calling it IMPOSS. This naming
02300 and specializing is central to BEING creation: a BEING recognizes an
02400 instance of itself, and decides either to insert a call to itself or
02500 else to insert a call to a specialized version of itself. If any
02600 nontrivial decisions must be made, and can be settled at synthesis
02700 time, then the latter alternative is chosen. CONTRADICTS is too
02800 general a BEING to be called in an inner loop, so its content will
02900 be hammered out at synthesis time. On the other hand,
03000 FORSOME is so primitive that no specialized
03100 version of it is written normally.
03200 Here is the way this piece of the dialogue actually appears.
03300 The user's reponses are italicised.
03400 The system informs the user of
03500 where it is by simulating a cursor pointing into a graph of program
03600 code. This is analogous to the textual and dynamic indices which
03700 [Dijkstra] suggests.
03800 .NOFILL
03900
04000 PLEASE TYPE IN A LOGICAL EXPRESSION WHICH IS TRUE WHEN WE TERMINATE
04100 THE LOOP, AND IS FALSE OTHERWISE.
04200
04300 SHOULD I DISCUSS RAMIFICATIONS?⊗4NO⊗*
04400
04500 USER: ⊗4(ANY FEATURE IN MODEL:FEATURES IS INCOMPATIBLE
04600 WITH SCENE:FEATURES)⊗*
04700
04800 PUP WANTS USER TO TYPE IN NAME FOR SPECIALIZED VERSION OF CONTRADICTS.
04900
05000 USER: ⊗4IMPOSS⊗*
05100 .FILL
05200 Later in the dialogue, PUP6 decides it must
05300 expand the function IMPOSS. The CONTRADICTS BEING is again called on; this
05400 time it is asked how to write a specialized version of a
05500 contradiction test. It replies that SOME_OF the following types of
05600 contradiction may occur: PROBABILITY:0, PROBABILITY:1, and
05700 PROBABILITY:ε(0,1). This is the germ of the idea for the
05800 MUSTNOT/MUST/MAY categorization of features. The SOME_OF BEING takes
05900 control, and asks if the decision can be deferred. The DEFERRAL
06000 BEING looks about, first asking if there is any non-null piece of
06100 code that all three have in common. This fails, and eventually the
06200 DEFERRAL BEING reports failure. SOME_OF sees it has no basis upon
06300 which to form a guess, and wants somebody to ask the user. The
06400 ASK_USER BEING takes over, and trivially finds out what exactly it is
06500 that PUP6
06600 wants to learn. The names of the three choices are so cryptic that
06700 their WHAT and HOW parts are printed out to the user, as well as
06800 their names. The user types back his choices, in our case all three.
06900 SOME_OF composes three new function calls, separated by a
07000 conditional:
07100 .B
07200
07300 (COND ( (IS_OF_TYPE F PROBABILITY:0_PART_OF_M_FEATURES)
07400 (PROBABILITY:0_CONTRADICTION F S_FEATURES))
07500 ( (IS_OF_TYPE F PROBABILITY:1_PART_OF_M_FEATURES)
07600 (PROBABILITY:1_CONTRADICTION F S_FEATURES))
07700 ( (IS_OF_TYPE F PROBABILITYε(0,1)_PART_OF_M_FEATURES)
07800 (PROBABILITYε(0,1)_CONTRADICTION F S_FEATURES)))
07900 .E
08000 TRICHOTOMY recognizes this as a split on a function's values
08100 being =0, =1, or between zero and one. It asks whether this
08200 particular function can only range over the interval [0,1].
08300 PROBABILITY answers affirmatively, so SOME_OF replaces the final
08400 IS_OF_TYPE test by the constant T. Later on, PUP6 must worry about
08500 the other two tests, and about the three contradiction predicates.
08600 These latter entities know (their ENCODABLE parts tell them) that
08700 they are immediately encodable. A probability=0 contradiction means
08800 that arg1 must not occur in the world arg2 yet it does. So the
08900 META-CODE of the PROBABILITY:0_CONTRADICTION BEING is defined as
09000 (MEMBER arg1 arg2). This corresponds to a MUSTNOT feature F which is
09100 present in the world (in the set of S_FEATURES of the scene.) A
09200 probability=1 contradiction occurs when a feature arg1 must occur in
09300 the world arg2, yet it doesn't. So its definition is simply (NOT
09400 (MEMBER arg1 arg2)). It is impossible for a feature with probability
09500 in (0,1) to be in contradiction with any world (lacking negated
09600 features), so this third predicate is defined as the constant NIL.
09700 That is, if F is a MAY feature of the model M, then there can be no
09800 contradiction between F and ⊗4any⊗* features of the scene S.
09900 When a BEING is said to do or recognize or know something, as
10000 in the preceding and following paragraphs, what is actually meant is
10100 that one or more of its parts specificly encode that knowledge. All
10200 the parts of the hundred BEINGs in PUP6 were coded by hand, not by
10300 each other. They then can encode other BEINGs, interacting only via
10400 the dialogue.
10500 The IS_OF_TYPE BEING recognizes that it must work hard to
10600 replace each of the two case tests, unless M_FEATURES is organized
10700 permanently into three parts (thus permitting the complex function
10800 "IS_OF_TYPE" to be replaced by the simple one "MEMBER" in the above
10900 piece of code). The STRUCTURE_INDUCING BEING will take over, to probe
11000 the permissability and the difficulty of such a constraint. It finds
11100 nothing about this tripartite structuring which could damage any
11200 earlier synthesized code, and asks the user's blessing. Notes are
11300 added to the list of coding warnings, stating that any reference to
11400 the entire list of M_FEATURES must be replaced by either APPEND of
11500 the three new lists, or else by three separate statements. GET_NAME
11600 is indirectly called, and he has the user name the three new sets of
11700 features; say he responds by calling them MUSTNOT, MUST, and MAY. The
11800 system would at this point say to draw an arrow on its graph of code,
11900 from the function call (IMPOSS F S_FEATURES) to the new block of code:
12000 .B
12100
12200 (COND ( (MEMBER F MUSTNOT_PART_OF_M)
12300 (MEMBER F S_FEATURES))
12400 ( (MEMBER F MUST_PART_OF_M)
12500 (NOT (MEMBER F S_FEATURES))
12600 ( T (COMMENT THIS "T" REPLACES "MEMBER F MAY_PART_OF_M")
12700 NIL))
12800 .E
12900 This is now the META:CODE part of the new BEING called IMPOSS.
13000 Most of the other parts are taken from its generalization, namely
13100 CONTRADICTS. During the course of writing this piece, however, some
13200 of these parts would be slightly changed. For example, its reason
13300 for existing would be strengthened when the simple MEMBER function
13400 calls replaced the slow IS_OF_TYPE BEING calls.
13500 Here is the actual transcript of this part of the dialogue; it may also
13600 be seen (with the names slightly changed) in the appendix, on
13700 pages A5.10 to A5.12.
13800
13900 .NOFILL
14000
14100 MOVE CURSOR TO IMPOSS TYPE OF CONTRADICTS
14200
14300 SORRY TO BOTHER YOU, BUT I CAN NO LONGER DEFER THIS SOMEOF DECISION
14400 (PROBABILITY=1:CONTRADICTION PROBABILITY=0:CONTRADICTION
14500 PROBABILITY>0&<1:CONTRADICTION)
14600 SINCE THE DECISION IS SOME:OF, TYPE ANY ORDERED SUBSET OF:
14700 (A .... PROBABILITY=1:CONTRADICTION)
14800 (B .... PROBABILITY=0:CONTRADICTION)
14900 (C .... PROBABILITY>0&<1:CONTRADICTION)
15000
15100 <discussion of the ramifications of each of these types of contradiction>
15200
15300 USER: ⊗4(A B C)⊗*
15400
15500 (I RECOMMEND THAT MODEL:FEATURES BE STRUCTURED INTO (AT
15600 LEAST ALONG ONE DIMENSION) THESE 3 PIECES:
15700 (PROBABILITY=1:CONTRADICTION:PART:OF:MODEL:FEATURES
15800 PROBABILITY=0:CONTRADICTION:PART:OF:MODEL:FEATURES
15900 PROBABILITY>0&<1:CONTRADICTION:PART:OF:MODEL:FEATURES).
16000 PLEASE TYPE BACK YES, NO, OR UNSURE.)
16100
16200 USER: ⊗4YES⊗*
16300
16400 PUP WANTS USER TO TYPE IN A SHORTER NAME FOR
16500 ( PROBABILITY:1:CONTRADICTION:PART:OF:MODEL:FEATURES)
16600 USER: ⊗4MUST:FEATURES⊗*
16700 .
16800 .
16900 .
17000 DRAW A LINE FROM THE FUNCTION CALL (IMPOSS FEATURE SCENE:FEATURES)
17100 OF THE FUNCTION IMPOSS TO THIS NEW PIECE OF CODE, WHICH
17200 IS ITS BODY:
17300
17400 (IMPOSS
17500 (LAMBDA (ARG1 ARG2)
17600 (COMMENT IN ALL CALLS TO DATE, ARG1 IS INSTANTIATED AS FEATURE
17700 AND ARG2 IS INSTANTIATED AS SCENE:FEATURES)
17800 (COND
17900 ((MEMBER ARG1 MUST:FEATURES)
18000 (COMMENT ARG1 OCCURS WITH PROBABILITY 1, SO IT HAD BETTER BE
18100 IN ARG2, THE RELEVANT PIECE OF THE WORLD)
18200 (NOT (MEMBER ARG1 ARG2))))
18300 ((MEMBER ARG1 MUSTNOT:FEATURES)
18400 (COMMENT SINCE ARG1 SHOULD NEVER OCCUR, WE HAVE A
18500 CONTRADICTION IF IT IS A MEMBER OF ARG2)
18600 (MEMBER ARG1 ARG2)))
18700 (T (COMMENT WE MAY OR MAY NOT HAVE ARG1 IN ARG2; EITHER
18800 CASE IS ALLOWABLE; SO WE
18900 NEVER HAVE A CONTRADICTION)
19000 NIL))))
19100
19200 IMPOSS has now been redefined as a BEING.
19300
19400 (IN ALL CODE GENERATED,
19500 ALL OCCURRENCES OF MODEL:FEATURES HAVE BEEN REPLACED
19600 BY (APPEND MUST:FEATURES MUSTNOT:FEATURES MAY:FEATURES))
19700
19800 .FILL
19900 Notice that only a few messages have passed
20000 from user to PUP6 during all this processing. The user has the feeling
20100 of merely directing, constraining, and watching the activities of a
20200 busy programmer. Unfortunately, "the user" is not generic; there
20300 was only one successful user. As was mentioned earlier, PUP6 insists
20400 on doing structured programming, so its traces are superficially
20500 similar to macro expansion. Despite this concentration on planning,
20600 no BEINGs system
20700 should halt so long as any details remain.
00100 .NEXT PAGE
00200 .EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {PAGE},REALITY: RESULTS)
00300 ⊗27. REALITY: RESULTS⊗*
00400 The nature of the task is of course central to any discussion of
00500 performance. For that reason, this section will deal more with automatic
00600 programming than with representing knowledge. The success of an AI effort
00700 can be assessed only where accepted standards of intelligence exist.
00800 The character of the dialogue (described in Section 6 and in
00900 Appendix 5) is, of course, one important measure of the intelligence
01000 of an AP system. One which asked "What is the first instruction?
01100 What is the second...?" would be universal but worse than useless. In
01200 this section are some proposed questions one should ask when
01300 confronted by a new AP system
01400 which generates code heuristically from a dialogue.
01500 The answers pertaining to PUP6 are parenthesized after each question.
01600 Only capsules are given; fuller answers are located elsewhere.
01700 The questions break into two categories. First, one wants to
01800 know what the system does. Most important, does it write a program?
01900 (yes.)
02000 If so, how complex is that task, and what is the program
02100 specification like? (a concept formation program, several pages long,
02200 from one specific protocol dialogue).
02300 How precise must the user be: may he err (no),
02400 forget (no), change his mind? (yes, in limited cases.)
02500 How detailed must his dialogue be? (by construction, just about as
02600 detailed as if he were talking to a CS grad student programmer.) How
02700 closely does the dialogue determine the details of the final code?
02800 (some inferences are made, and several representational choices, but
02900 much of the
03000 final code is clearly determined by the precise user responses.)
03100 How does the user know where he is during the dialogue? (simulated cursors
03200 pointing to a graph representing synthesized code.)
03300 Quite seriously, an important question is whether the system
03400 writes a second program. (yes.)
03500 If so, how does it relate to the first one
03600 synthesized? (both are inductive inference LISP programs.)
03700 How much of the AP system is actually used in writing
03800 ⊗4both⊗* programs? (49 BEINGs out of 79.)
03900 One should ask what the full range of programs is
04000 which the system has successfully synthesized. (the concept former, the
04100 grammatical inferrer, and the simple information manipulation system.)
04200 The dual questions to
04300 these inquire whether a program may be generated by several different
04400 (in the sense of rephrasing and in the sense of reordering the subtasks)
04500 dialogues (theoretically, but not practically),
04600 and what the range of variability is. (theoretically large, but
04700 practically quite limited.) Similarly, what
04800 about the target language: is it a parameter? (no, always the same.)
04900 How does it relate to
05000 the language the system is written in? (both written as BEINGs in
05100 INTERLISP.)
05200 Does the system modify as well as write code? (yes, but not
05300 as its major mechanism.) If so, can
05400 it modify anybody's, or only those programs it has written itself?
05500 (only its own, and only in simple ways.)
05600 What is its "style" of programming? (many supplementary comments,
05700 fairly clean structured programs only.)
05800 One also wishes to know the size
05900 of the tool as well as the size of the job: How does the system size
06000 compare to target program size? (one order of magnitude larger.)
06100 Efficiency considerations are often the crucial
06200 pragmatic ones. Economics and current hardware restrict the amount of
06300 computation which may be done in toto; the expected lifetime of the
06400 universe restricts us from using the most "elegant" algorithms; and
06500 human patience restricts the interaction delay time (to a minute or
06600 two of real time). One must therefore ask things like
06700 how much time and space it requires, how long a delay there is
06800 between user inputs, etc. (one CPU hour, 100K, under a CPU minute
06900 between responses.)
07000 The second class of questions concerns the theoretical side
07100 of the AP system. What new ideas is it meant to experiment with?
07200 (this is the subject of most of the preceding text; see esp. section
07300 3.) How
07400 do each of these ideas fare? (many surprises; this is the subject of
07500 most of the remainder of this paper; see esp. section
07600 8.) Does it write its code in the right way?
07700 (it asks the right questions of the user at just the proper
07800 times with respect to the original protocol.)
07900 How extendable is it: how difficult is it to add new pieces
08000 of knowledge and to modify old ones? (theoretically easy, practically it
08100 requires familiarity with the system.) Could it write programs in
08200 various fields (probably), in various styles (possibly), in various sizes?
08300 (the three target programs differ by less than one order of magnitude.)
08400 How is knowledge represented internally? (BEINGs, assertions,
08500 demons.) Is any of it
08600 duplicated? (not much above the LISP language level; some universal
08700 knowledge is factored out; e.g., how to CHOOSE-FROM a set of BEINGs.)
08800 If so, what and why? (some, by laziness; e.g.,
08900 how to bind variables.) Why doesn't this system solve the AP
09000 problem? (it was mistakenly thought that the problems of dialogue were not
09100 central to "the AP problem.")
09200 Detailed answers to most of the these questions are scattered
09300 throughout the earlier sections of this paper. Below are its answers
09400 in detail to the remaining questions.
09500 Let us briefly describe GI and INF, the second and
09600 third programs PUP6 synthesized. GI is a simple
09700 grammatical inference program. It builds up a set of plausible rules,
09800 rather than enumerating through the space of all grammars. Yet it
09900 lacks most of the "tricks" of the best g.i. programs. The user
10000 repeatedly specifies a string, labelled LEGAL, ILLEGAL, or ??. In the
10100 latter case, GI must print out its guess and accept the correct label
10200 from the user. In all three cases, it must update its set of
10300 plausible rules to be at least consistent with all positive and
10400 negative instances observed. In some versions of GI the user coaxes
10500 PUP6 to generate, a parse tree may be maintained and inspected; in
10600 other versions, just a list of the rules used during a parse is kept.
10700 INF is a data-retrieval-on-keys system.
10800 The user repeatedly types
10900 in a request to insert, delete, or inspect a record (e.g., INSERT:
11000 PASSENGER Jones FLIGHT 741 FROM SFO TO LAX CARRIER TWA LEAVE 7:15
11100 ARRIVE 8:00). Any unspecified fields are treated as dont't cares;
11200 thus the request is matched against entries in the data base.
11300 The table below shows how each type of knowledge was used in
11400 writing the three target programs. All numbers refer to BEINGs.
11500
11600 .BEGIN
11700 .GROUP
11800 .NOFILL
11900 .FONT 7 "FIX20"
12000 .FONT 8 "NGB30"
12100 .SELECT 7
12200 .BREAK
12300
12400 .ONCE CENTER
12500 ⊗8U S E D I N S Y N T H E S I Z I N G⊗*
12600
12700 TYPE OF CF CF CF CF GI INF not Crea Crea Crea Total
12800 KNOWLEDGE GI GI INF only only only used -ted -ted -ted BEINGs
12900 INF only only ever in CF in GI in INF
13000
13100 Programming 39 7 5 5 3 1 14 52 27 21 174
13200 Domain-Specific 0 3 0 9 8 1 5 4 10 3 43
13300 Total BEINGs 39 10 5 14 11 2 19 56 37 24 217
13400 .END
13500
13600 The high percentage of programming BEINGs which were used in all
13700 three dialogues is exciting. The three domain-specific BEINGs used
13800 in both CF and GI sessions indicate that they may be Inductive
13900 Inference domain specific. They aren't used in INF, which is not an
14000 inductive inference task. All three deal with partitioning a domain.
14100 A specialization of a general programming BEING is listed as
14200 a programming BEING still (in the CREATED columns of the above
14300 table.) This is because it remains sufficiently independent to be
14400 used in many ways, conceivably in many different programs.
14500 The style of the synthesized programs is constrained since
14600 all code must be BEINGs. At a lower level, there are many trivial
14700 inefficiencies which are passed through a BEING which is to optimize
14800 LISP programs out of context, at a low level. This BEING is
14900 vacuous now, but may soon contain a LISP optimizer being written by
15000 A. Cohn of the SAIL AP group. Low level efficiency was intentionally
15100 ignored to expedite work on PUP6. Nevertheless, the final code
15200 produced runs in about the same time as the hand-coded versions
15300 (e.g., a few seconds per scene for CF). It is several times as long,
15400 though, since it must be able to answer questions about what it's
15500 doing as it runs. The program produced by the system-player during
15600 the original protocol lacked this ability, of
15700 course.
15800 Although BEINGs can theoretically handle
15900 user errors, PUP6 was set up expecting that the user would never err
16000 or forget. He could, after the program was finished, try it out and
16100 describe how he wished it changed. Occasionally, PUP6 actually make
16200 the right modifications. For example, INF,
16300 the simple data storage and retrieval on keys
16400 system which was written, was supposed to accept, access, and eliminate
16500 reservations. After the synthesis is finished, the user tries
16600 out the program and finds that he is unable to delete more than one
16700 reservation with any single command. He complains about this, and
16800 PUP6 modifies the program so that he may specify a pattern, and all
16900 reservations matching that pattern will be purged. While
17000 assumptions of absolute
17100 user reliability are reasonable for little programs,
17200 they break down when the tasks reach the size of tens of pages and
17300 hours.
17400 Good measures of concentration of intelligence are not yet
17500 available. The only alternative is to present ephemeral numerical
17600 efficiency data, which now follows. PUP6 is 200 pages long when
17700 PRETTY-PRINTED, and has synthesized three programs, 7, 20, and 30
17800 pages long (1, 4, and 6 pages, when coded by hand.)
17900 Two important factors are omitted when simply comparing system
18000 and target lengths. First, one might improve any such measure by simply
18100 decreasing the size of a given system. This is wrong, since, e.g.,
18200 removing all the comments from a program shouldn't increase its
18300 intelligence! Secondly, the total amount of distinct target programs
18400 should be considered. Compilers turn out programs small compared to
18500 themselves, but are valuable because of the vast variety of such programs
18600 they can put together.
18700 This factor reflects how much of the "guts" of the system can be used in
18800 writing many programs.
18900 PUP6 takes 60 cpu minutes to produce CF (compiled INTERLISP
19000 code, run on a PDP-10 TENEX system). During this time,
19100 300K characters get typed out to the user, who reponds with about
19200 4K himself. The dialogue lengths are best specified in characters,
19300 since often the user will supply simply a number or a letter or a
19400 YES/NO reply. Dividing these by a hundred, one can relate them to
19500 target and system lengths in lines. Even the character counts are
19600 very rough, because the format of the AP dialogue can easily be
19700 varied by a couple orders of magnitude. The mean wait time (between
19800 the user's input and the next machine output) is several seconds. The
19900 longest delay between successive user inputs is 1 CPU minute.
20000 Unfortunately, PUP6 requires 100K to run in, which (with INTERLISP)
20100 exhausts the virtual memory of the current hardware being used. One
20200 would lose vast amounts of time by using intermediate storage devices
20300 or by running consecutive communicating jobs. Efficient use of multiple
20400 processors and of extended core storage might be made.
20500 INF was one fifth the size of CF, and took about a seventh
20600 as long to generate. The dialogue was shorter by a factor of three. The
20700 dialogue for the CF target program was too long and tiresome; the problem
20800 was even more acute for the INF program.
20900 Most of the theoretical questions are answered by the very
21000 design of the system. Its ideational foundation has been discussed.
21100 When the user sticks close to the original protocol, PUP6 asks the
21200 right questions at the right times because of its genesis from that
21300 annotated protocol. The second and third programs were attempted
21400 only to test its flexibility, and the results were mixed.
21500 First the bright side. The increment to PUP6 to enable it to
21600 write the GI and the INF programs is encouragingly small. Almost all
21700 the programming-knowledge BEINGs are called in writing more than one
21800 of the programs. It is now clear that very domain-specific BEINGs
21900 were in control at the early, high levels. Later, more general BEINGs
22000 took over, followed by pure programming BEINGs. The middle category
22100 would include inductive-inference-specific
22200 BEINGs like PARTITION_A_DOMAIN.
22300 Regrettably, incrementing the system with new domain-specific
22400 BEINGs is not feasable for the average user. To add a BEING, he must
22500 specify all of its relevant parts. Each is inputted either as LISP
22600 code, as an English sentence PUP6 is capable of interpreting, an
22700 English sentence PUP6 is just supposed to remember as a canned
22800 response, or by pointing to a part of an existing BEING and saying
22900 "like that one, except ...", where the ellipsis must be
23000 very simple. The interactions between the BEINGs, and the existing
23100 set of BEINGs, need not be fully understood; but the set of allowable
23200 assertion templates, the mechanisms by which each part is used, the
23300 special data types involved (VECTOR, TUPLE), and the precise actions
23400 of each new part ⊗4must⊗* be known in order to safely inject a new
23500 BEING.
23600 This may be a result of the small amount of knowledge in PUP6. One would
23700 hope that a BEINGs system which was expert in a domain could assist the
23800 user in adding new domain-specific BEINGs, in the same way that the
23900 BEINGs which make up the target code are synthesized, through dialogue.
00100 .NEXT PAGE
00200 .EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {PAGE},THEORY: CONCLUSIONS)
00300 ⊗28. THEORY: CONCLUSIONS⊗*
00400 The strengths and weaknesses of both BEINGs and PUP6 are
00500 reviewed.
00600 This experiment has helped clarify some
00700 of the potential problems facing
00800 future AP work.
00900 While the number of BEING-parts is
01000 unimportant, its magnitude (a few tens) may have significance to AP.
01100 The fact that is isn't ~1 may help explain the difficulty with predicate
01200 calculus representations; the fact that it isn't ~1000
01300 may mean that the AP
01400 problem is tractible.
01500 Some of the ideas discussed at the beginning of the paper
01600 have proven themselves to be useful in getting PUP6 to work.
01700 Little programs
01800 can indeed be treated as if their essence is nothing more than a
01900 collection of answers. The gain from standardization is
02000 conceptually easy
02100 addition of pieces to the system; one "merely" adds new BEINGs to the
02200 community. Their interactions with all the existing BEINGs needn't be
02300 known in advance. As was discussed in the previous section, the
02400 actual addition is beyond the power of the untrained user.
02500 Indications are that one ⊗4can⊗* locate relevant
02600 information by organizing the knowledge in a pool, with each piece
02700 (i) responsible for recognizing when it is relevant and (ii)
02800 indicating new relevant information indirectly via nondeterministic
02900 pattern-directed retrievals and assertions. Notice that this puts
03000 all control structure into the hands of the BEINGs; there is no
03100 central monitor in PUP6. A BEING's answers may at various times
03200 indicate that it should be chosen to be in control, and it will then
03300 take over. Notice also that this relevancy problem is central to
03400 program maintenance as well as synthesis. It is not clear whether
03500 or not this really beats the exponential growth of this problem.
03600 The fact that target code is in the format of BEINGs limits
03700 the size of the target programs (≥ one page) and their efficiency (a
03800 BEING-call is a very slow and intricate process) and of course their
03900 style. The most startling result -- which should have been forseen --
04000 was that "intelligent" target code is synthesized. This was mentioned
04100 casually in the IDEAS section,
04200 but its importance is clear: the target code
04300 is self-commenting in the strong sense that the generated
04400 code can answer any
04500 (of our set of 29) questions about itself. Those which make sense at
04600 compile-time can be asked then; those which make sense during
04700 execution may be asked then. For example, CF begins running. After
04800 several scenes have been processed, CF is waiting for a new one. If
04900 the user interrupts and asks what it is doing, CF will reply
05000 "awaiting user input of a brand new scene." One can ask why, how, who
05100 will be affected, and so on, interrupt as frequently as desired --
05200 even after each transfer of control from one BEING to
05300 another. The actual questions and
05400 responses are not very impressive, but they are at least at the same
05500 level as those which can be gotten from PUP6 itself as it runs.
05600 The set of questions the user was expected to want to ask the
05700 system is similar to the questions one BEING wants to ask another.
05800 So when the "nice" user interrupts, his questions are almost always a
05900 simple retrieval from a property list (a GETP or a composition like
06000 EVALπ.GETP). When the average user interrupts, his questions are
06100 often unintelligible to PUP6.
06200 Meaningful use of comments proved helpful. As an example, the
06300 comment at the end of the main outer loop was "COMMENT, INFINITE LOOP
06400 IN THIS PROG" (see page A5.10) for most of the session. Near the end
06500 of the session, the CLARIFY_IMPROBABLE_SITUATION BEING recognizes
06600 this as a warning, works on introducing a breakaway test, and then
06700 replaces the comment by one indicating that no infinite loop exists
06800 there anymore (see page A4.4). The advantage to embedding our
06900 insertions in the code this way is that, at any stage, the user can
07000 inspect the code and get something meaningful out of the comments
07100 which are present.
07200 The careful bookkeeping actually did eliminate some
07300 carelessness errors, though it had no effect on user errors or later
07400 program maintenance directives. These latter processes are less
07500 ill-defined than blind debugging, and in fact are about the same as
07600 programming itself [Dijkstra]. The deferral of decisions has the
07700 nice corollary of reducing (though not minimizing) communication with
07800 the slow user channel.
07900 Synthesizing a new,
08000 clean target program probably would require
08100 adding a few domain-independent BEINGs and several domain-specific
08200 BEINGs, and generalizing several parts of several existing BEINGs.
08300 Since the dialogues for GI and INF were not studied before-hand,
08400 their acceptability would have demonstrated the success of the
08500 system. Most of the existing BEINGs were used in generating these
08600 new programs, but a few new BEINGs had to be added. This addition
08700 process required detailed knowledge of the PUP6 system, not just of
08800 the domain. Equally
08900 discouraging, the dialogue to write INF is too long and detailed
09000 for the task at hand. It also seems that the front end is too
09100 brittle to allow anyone unfamiliar with the system to easily work
09200 with it.
09300 The need for flexible communication stems only
09400 partially from inter-user differences. A serious and unexpected
09500 source of conflict here is the amount of inference the user wants
09600 done. This level is relatively subjective, and may fluctuate rapidly
09700 even with one user writing one program. Perhaps there should be a
09800 dial he can set. At one extreme, the system would ask the user to
09900 verify even the most trivial inductions. At the other extreme
10000 setting, the system would probably write the target program after
10100 just a few brief user inputs. The user would then try out one program
10200 after another, interjecting just one or two comments each time, after
10300 which the system would come up with the next version. This program
10400 modification mode seems appropriate for someone ignorant of LISP, who
10500 nevertheless has the I/O behavior of his target clearly in mind.
10600 Some of the BEING parts proved embarrassingly unnecessary.
10700 The CO-REQUISITES part was never used. The only activity which had
10800 to be done concurrently was demon activation. The AFFECTS part was of
10900 interest to the user occasionally, but never to any BEING. The
11000 EFFECTS part originally had a twin, describing what would happen if
11100 each BEING were ⊗4not⊗* called right now. In each case, this was
11200 merely a trivial restatement of the frame problem. So, like STRIPS
11300 [Fikes], PUP6 ignores the frame problem: all changes must be
11400 explicit.
11500 Much of PUP6's comments are boring and unnecessary; this was
11600 felt to be an engineering problem which would be ignored in all but a
11700 "marketable" AP system. This view was probably incorrect. One of the
11800 most severe AP problems is having the system inform the user of
11900 precisely what he should know -- no more nor less. This requires a
12000 sophisticated user model cleverly interfaced to the current
12100 programming task.
12200 Another problem with large, long dialogues is user error. A
12300 human has great difficulty keeping "on top" of everything. He may
12400 get lost, forget, change his mind, or misunderstand. Again, this
12500 problem was originally considered ignorable, but has shown itself to
12600 be a limiting practical factor in wide accessability. It was
12700 necessary to create a forgetful-user demon to prevent anaphoric
12800 reference to something which, though uniquely determined, hadn't been
12900 mentioned within the past several seconds.
13000 Related to this is the problem of keeping
13100 the user informed of where he is. PUP6 simulated a continuous display
13200 of the graph of the current partial program, augmented by static and
13300 dynamic cursors. This simple
13400 use of dynamic and textual indices seems
13500 insufficient. The user was still often confused, wishing a section
13600 referred to not by pointing but rather by a brief, meaningful (to him
13700 only!) phrase. This may also be one of the major AP problems which
13800 must be studied further.
13900 These worries about large dialogues arise because future AP
14000 systems are viewed as tools for writing programs which humans simply
14100 cannot manage currently: viable natural language systems, huge
14200 operating systems, better AP systems.
14300 One might argue against ever needing a
14400 system whose target programs will be longer and more complex than the
14500 system itself. First, empirically, optimizing compilers are viable
14600 and yet they dwarf almost all the code they generate. Second, as the
14700 complexity of the transformation increases, the length of a compiler
14800 increases rapidly. For a truly intelligent AP system, one might be
14900 willing to tolerate a program several times as large as anything it
15000 could produce.
15100 An argument exists to counter this one. First, one might
15200 object to drawing an analogy from compilers; many entities are
15300 capable of producing things more sophistocated than themselves,
15400 larger than themselves, etc. (consider evolution). Second, it seems
15500 that there is a manageable body of information which one needs master
15600 to do programming (informal). Viewed differently, one can
15700 write programs as long as he wishes if the program is designed in a
15800 clean way. Thus the size of AP systems will probably
15900 level off (albeit huge
16000 compared to existing programs) even as the size and complexity of
16100 their generated code continues to increase and, eventually, surpass
16200 them. Finally, we must consider why we want a good AP system: to
16300 help us write large programs easily, programs which might be
16400 unmanageable today. For this reason alone, our AP system must be
16500 able to deal with programs larger than itself.
16600 The whole design of BEINGs is
16700 oriented toward this large-scale end. One cannot write tiny,
16800 super-efficient programs using BEINGs, any more naturally than one
16900 can generate efficient machine code using a high level language.
17000 A BEINGs system might simulate this activity, but it would be as
17100 awkward and opaque as if they were asked to simulate volleyball. By
17200 relinquishing more and more control to the computer language
17300 environment, the programmer sacrifices specialization of the final
17400 code for ease of constructing it and for its greater size and
17500 complexity.
00100 .NEXT PAGE
00200 .EVERY FOOTING(⊗5Fourth Draft .... {DATE},page {PAGE})
00300 ⊗29. ACKNOWLEDGEMENTS⊗*
00400
00500 There are, of course, countless ideas embodied in any
00600 concrete project. Sweeping philosophical assumptions are made simply
00700 by deciding to do any type of programming [McCarthy], even moreso with
00800 Automatic Programming. Any
00900 Program-Understanding Program should include the best parts of all
01000 the best old ideas. PUP6 relies on concepts gleaned from Actors
01100 [Hewitt], Demons [........], heterarchy [.....], structured
01200 programming [Dijkstra], assertional data bases and flexible data
01300 types [Rulifson], pattern-directed invocation of procedural knowledge
01400 [Poincare'], the paradigm of AP by dialogue [Floyd],
01500 and studies on program
01600 specification techniques [Green]. Of course this list is incomplete;
01700 sophisticated ideas are captured in the languages themselves: QLISP
01800 [Reboh], INTERLISP [Teitelman], LISP [McCarthy2], and English
01900 [Anonymous]. To this rich store, one may achieve new heights merely
02000 by synergy.
02100 Any success of the BEINGs project, as well as the precursor
02200 PUP programs [Green] is due in large measure to the
02300 creative energy of C. Cordell Green. I have
02400 also drawn upon discussions with
02500 D. Barstow, B. McCune, D. Shaw, E.
02600 Sacerdoti, L.
02700 Steinberg, and R. Waldinger. The generosity of SRI, in providing
02800 computer time and language consultations, should not go unmentioned.
02900 Also valuable were the critical readings of this paper by R. Davis
03000 and T. Winograd.